#include <iostream>
#include <vector>
using namespace std;

class Solution 
{
private:
    bool isValid(vector<vector<int>>& sudoku, int row, int col, int val) 
    {
        // 检查行，
        for (int j = 0; j < 9; j++) 
        {
            if (sudoku[row][j] == val) return false;
        }
        
        // 检查列
        for (int i = 0; i < 9; i++) 
        {
            if (sudoku[i][col] == val) return false;
        }
        
        // 检查3x3宫格
        // 开始行，先整除3再乘3
        // 范围0~2
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) 
        {
            for (int j = startCol; j < startCol + 3; j++) 
            {
                if (sudoku[i][j] == val) return false;
            }
        }
        
        return true;
    }

    // 一股D味的函数名
    // 以后我也backtrack()
    void backtrack(int row, int col, int &count, vector<vector<int>>& sudoku) 
    {
        // 
        if (row == 9) 
        {
            count++;
            return;
        }
        
        if (col == 9) 
        {
            // 如果到达尽头？？？就再头开始
            backtrack(row + 1, 0, count, sudoku);
            return;
        }
        // 如果col为9，直接主动让row加一，强制解决递归
        
        if (sudoku[row][col] != 0)  // 这里是如果不为零，就继续下一列
        {
            backtrack(row, col + 1, count, sudoku);
            return;
        }
        
        // 在递归调用过程中，他会一直让col++直到调用下一个row为止 : 38行
        // 使用for循环遍历获取所有的1~9
        for (int val = 1; val <= 9; val++) 
        {
            // 
            if (isValid(sudoku, row, col, val)) 
            {
                sudoku[row][col] = val;
                backtrack(row, col + 1, count, sudoku);
                sudoku[row][col] = 0; // 回溯
            }
        }
    }

public:
    int solve() 
    {
        int count = 0;
        vector<vector<int>> sudoku(9, vector<int>(9, 0));
        backtrack(0, 0, count, sudoku);
        return count;
    }
};

int main()
{
    Solution *s = new Solution();
    cout<<s->solve()<<"\n";    
    return 0;   
}